Optimized Resolvent Splitting Examples¶

This notebook generates the figures in our paper, which outlines the use of a semi-definite programming framework for optimizing splitting algorithms which solve the following monotone inclusion problem:

\begin{equation} 0 \in \sum_{i=1}^{n} A_{i}(x). \end{equation}

It does so by finding valid matrices $L$ and $W$ for the following set of iterations, where bolded entries are lifted, i.e. $\mathrm{x} = (x_1, \dots, x_n)$:

\begin{align} \mathrm{x} &= J_{\mathrm{A}}\left(\mathrm{v}^{k} + \mathrm{L} \mathrm{x}\right)\\ \mathrm{v}^{k+1} &= \mathrm{v}^{k} - \gamma \mathrm{W} \mathrm{x}. \end{align}

$L$ is lower diagonal, so we work with a symmetrized matrix $Z = 2I - L - L^T$

In [1]:
import numpy as np
import oars
from oars.matrices import *
from oars.utils import *
from oars.pep import *
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib
# matplotlib.use('nbagg')
import seaborn as sns
sns.set()
from matplotlib.colors import CenteredNorm
import cvxpy as cvx
from collections import defaultdict
!mkdir -p figs

Our first example builds the matrices, which can be thought of as the graph Laplacians of communication graphs for the nodes in a distributed setting, to avoid specific communication paths.

We suppose a set of two clusters (0-2) and (3-5) which can only communicate within clusters and via a link between 0-3.

We then plot a Gantt chart for the distributed execution of the resulting algorithm.

We take as our objective function here the spectral norm of $Z-W$, which promotes graph similarity.

In [2]:
# Data for matrices in cluster example (6x6)
n = 6
Z_fixed = {(r,c):0 for r in range(4,6) for c in range(3)}
Z_fixed[(3,1)] = 0
Z_fixed[(3,2)] = 0

Z, W = getSimilar(n, fixed_Z=Z_fixed, fixed_W=Z_fixed)
In [3]:
# Figure 3
t = 0.016*np.ones(n)
l = 0.00025*np.ones((n, n))
l[0, 3] = 0.01
l[3, 0] = 0.01  
fig = getGantt(t, l, Z, W, title="Cluster Algorithm Parallelism", itrs=5)
fig.show()
fig.write_image("figs/fig_gantt.pdf")

In this example, we visually depict the different matrices generates by changing the objective function between maximizing algebraic connectivity, minimizing SLEM, minimizing total effective resistance, and minimizing the spectral norm of the difference of the matrices.

We also demonstrate the use of the getBlockMin function to build the constraint set for the SDP to guarantee that the nodes can execute in blocks. If the compute and communication times are constant and uniform, this guarantees that the algorithm can execute with the highest possible degree of parallelism possible for this type of splitting.

In [4]:
# Figure 4 helper
def cplot(W,Z):
    vmin = np.floor(np.min(np.minimum(W, Z)))
    cm = plt.cm.coolwarm
    fig, ax = plt.subplots(1, 2, figsize=(12, 6))
    x = -np.arange(n)
    y = np.arange(n)
    ax[0].pcolormesh(x, y, W, norm=CenteredNorm(), cmap=cm) #, vmin=vmin, vmax=2)
    ax[0].set_title(r"$W$")
    ax[0].axis('off')
    ax[0].set_aspect('equal')

    pc = ax[1].pcolormesh(x, y, Z, norm=CenteredNorm(), cmap=cm)
    ax[1].set_title(r"$Z$")
    ax[1].axis('off')
    ax[1].set_aspect('equal')

    # Add colorbar
    plt.tight_layout()
    
    fig.colorbar(pc, ax=ax.ravel().tolist())
    return fig
In [5]:
# Figure 4
n = 10
m = 2
Z, W = getBlockMin(n, m, objective=getMaxConnectivity)

fig = cplot(W, Z)

# Save as pdf

fig.savefig("figs/fig_block_fiedler.pdf")
No description has been provided for this image
In [6]:
# Figure 4
Z, W = getBlockMin(n, m, objective=getMinSLEM)

fig = cplot(W, Z)
fig.savefig("figs/fig_block_slem.pdf")
No description has been provided for this image
In [7]:
# Figure 4
Z, W = getBlockMin(n, m, objective=getMinResist)

fig = cplot(W, Z)
fig.savefig("figs/fig_block_resist.pdf")
No description has been provided for this image
In [8]:
# Figure 4
Z, W = getBlockMin(n, m, objective=getSimilar)

fig = cplot(W, Z)
fig.savefig("figs/fig_block_lw.pdf")
No description has been provided for this image

This example shows a comparison of the execution of the block designs when the computation times are not uniform, and the use of the getMinCycle function to generate designs which minimize the iteration time.

In [9]:
# Figure 5 (hangs if executed in Windows using Kaleido 0.1.0post1)
# try pip install kaleido==0.1.0post1
n = 6
t = np.ones(n)
l = np.ones((n,n))/10
t[0] = 6
t[2] = 6
t[3] = 6

for i in range(1, n//2+1):
    Zb, Wb = getBlockMin(n, i, objective=getMinResist)
    if i == 1:
        itrs = 6
    else:
        itrs = 7
    fig = getGantt(t, l, Zb, Wb, title=str(n//i)+"-Block", itrs=itrs)
    
    fig.write_image("figs/fig_misdp"+str(n//i)+"block.pdf")
    fig.show()

Z, W = getMinCycle(n, t=t, l=l, objective=getMinResist)

fig = getGantt(t, l, Z, W, title="Minimum Iteration", itrs=12)

fig.write_image("figs/fig_misdp_min_cycle.pdf")
fig.show()

In several of the following examples, we use the PEP formulation to find the contraction factor for the algorithm designs in two scenarios:

  1. $(n)$ 2-Lipschitz 1-strongly monotone operators

  2. $(n-1)$ 2-Lipschitz 1-strongly monotone operators, and 1 unrestricted maximal monotone operator (this simulates having the subdifferential of an indicator function over some convex set)

In the figure 6 example, we use a fixed step size of 0.5.

We then compare the different algorithm designs, including the spectral objectives using our SDP, and some existing designs in the literature.

In [10]:
# Figure 6 - contraction rate results
# fig_smoothstronglyconvex.ipynb
# Function to generate list of all test matrices
def getTestMatrices(n):
    cases = []
    Ws = []
    names = ['Full', 'MT']
    Lf, Wf = getFull(n)
    Mf = getMfromWCholesky(Wf)
    cases.append((Lf, Mf))
    Ws.append(Wf)
    Lmt, Wmt = getMT(n)
    Mmt = getMfromWCholesky(Wmt)
    cases.append((Lmt, Mmt))
    Ws.append(Wmt)
    i = n//2
    for obj in [getMinSLEM, getMinResist, getMaxConnectivity]:
        L, W = getBlockMin(n, i, objective=obj)
        M = getMfromWCholesky(W)
        cases.append((L, M))
        Ws.append(W)
        title = f"2-Block "+ obj.__name__
        names.append(title)
        
    return cases, names, Ws
    
def getMatrixContraction(cases, names, Lc=2, mu=1, gamma=0.5):
    '''Get contraction factors for matrix cases

    Args:
        cases (list): list of cases with L and M
        names (list): list of names
        Lc (float): Lipschitz constant
        mu (float): strong convexity parameter
        gamma (float): step size

    Returns:
        taus (dict): dictionary of contraction factors
    '''

    taus = {}
    for i, (L, M) in enumerate(cases):
        n = L.shape[0]
        
        ls = np.ones(n)*Lc
        mus = np.ones(n)*mu
        
        tau, _ = getReducedContractionFactor(L, M, ls, mus)
        taus[names[i]] = tau
        print(names[i], tau)
    return taus
In [11]:
# Figure 6 helper
def testFixedRate(start=4, end=31, lc=2, mc=1):
    tau_results = defaultdict(list) 
    for n in range(start, end, 2):
        print(f"Testing optimal rate on {n} nodes")
        ls = np.ones(n) * lc
        mus = np.ones(n) * mc
        cases, names, Ws = getTestMatrices(n)
        for i, (L, M) in enumerate(cases):
            tau = getReducedContractionFactor(L, M, ls, mus)
            tau_results[names[i]].append(tau)


    # Convert results to df
    tau_df = pd.DataFrame(tau_results)
    tau_df.index = range(start, end, 2)

    return tau_df
In [12]:
# Figure 6a
tau_df = testFixedRate(start=6, end=31)
Testing optimal rate on 6 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 8 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 10 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 12 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 14 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 16 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 18 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 20 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 22 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 24 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 26 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 28 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 30 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
In [13]:
# Plot figure 6a
fig, ax = plt.subplots()
tau_df.plot(ax=ax)

ax.set_xlabel("n")
ax.set_ylabel("Contraction")
ax.set_title(r"Fixed step size contraction with $n$ Lipschitz strongly monotone operators")
ax.legend(['Full', 'MT', '2-Block Min SLEM', r'2-Block Min Resistance (also min $\|Z-W\|$)', '2-Block Max Fiedler'], loc=(0.25,0.4))
fig.savefig("figs/fig6a.pdf", format="pdf", bbox_inches="tight")
No description has been provided for this image
In [14]:
# Figure 6b helper
def testFixedRateProj(start=4, end=31, lc=2, mc=1):
    tau_results = defaultdict(list) 
    for n in range(start, end, 2):
        print(f"Testing optimal rate on {n} nodes")
        ls = np.ones(n) * lc
        ls[n-1] = np.inf
        mus = np.ones(n) * mc
        mus[n-1] = 0
        cases, names, Ws = getTestMatrices(n)
        for i, (Z, M) in enumerate(cases):
            tau = getReducedContractionFactor(Z, M, ls, mus)
            tau_results[names[i]].append(tau)


    # Convert results to df
    tau_df = pd.DataFrame(tau_results)
    tau_df.index = range(start, end, 2)

    return tau_df
In [15]:
# Figure 6b
tau_df = testFixedRateProj(start=6, end=31)
Testing optimal rate on 6 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 8 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 10 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 12 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 14 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 16 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 18 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 20 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 22 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 24 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 26 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 28 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 30 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
In [16]:
# Plot figure 6b
fig, ax = plt.subplots()
tau_df.plot(ax=ax)

ax.set_xlabel("n")
ax.set_ylabel("Contraction")
ax.set_title("Fixed step size contraction with an unrestricted monotone operator")
ax.legend(['Full', 'MT', '2-Block Min SLEM', r'2-Block Min Resistance (also min $\|Z-W\|$)', '2-Block Max Fiedler'], loc="lower right")
fig.savefig("figs/fig6b.pdf", format="pdf", bbox_inches="tight")
No description has been provided for this image

In figure 7 we repeat the analysis, but using an optimal step size we derive from an extension of the dual of the PEP. This also demonstrates the use of the getReducedGamma function, which generates a step size which minimizes the contraction factor for the reduced version of the algorithm:

\begin{align} \mathrm{x} &= J_{\mathrm{A}}\left(-\mathrm{M}^{T} \mathrm{z}^{k} + \mathrm{L} \mathrm{x}\right)\\ \mathrm{z}^{k+1} &= \mathrm{z}^{k} + \gamma \mathrm{M} \mathrm{x}. \end{align}

where $M^T M = W$

In [17]:
# Figure 7 helper
def testOptimalRate(start=4, end=31, lc=2, mc=1):
    tau_results = defaultdict(list) 
    for n in range(start, end, 2):
        print(f"Testing optimal rate on {n} nodes")
        ls = np.ones(n) * lc
        ms = np.ones(n) * mc
        cases, names, Ws = getTestMatrices(n)
        for i, (Z, M) in enumerate(cases):
            _, tau = getReducedGamma(Z, M, ls, ms)
            tau_results[names[i]].append(tau)


    # Convert results to df
    tau_df = pd.DataFrame(tau_results)
    tau_df.index = range(start, end, 2)

    return tau_df
In [18]:
# Figure 7 helper
def plotTau(tau_df, title):
    fig, ax = plt.subplots()
    tau_df.plot(ax=ax)
    ax.set_xlabel("n")
    ax.set_ylabel("Contraction") #$\\tau$
    ax.set_title(title)
    ax.legend(['Full', 'MT', '2-Block Min SLEM', r'2-Block Min Resistance (also min $\|Z-W\|$)', '2-Block Max Fiedler'], loc="center right")
    #ax.legend(loc='center right')
    #plt.show()
    return fig
In [19]:
# Figure 7
tau_df = testOptimalRate(start=4, end=31)

tau_df.to_csv("figs/fig_opt_gamma_strong.csv", index=False)
Testing optimal rate on 4 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 6 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 8 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 10 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 12 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 14 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 16 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 18 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 20 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 22 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 24 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 26 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 28 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 30 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
In [20]:
# Figure 7
#tau_df = pd.load_csv("fig_opt_gamma_strong.csv")
fig = plotTau(tau_df, "Contraction over $n$ Lipschitz strongly monotone operators")
fig.savefig("figs/fig_opt_gamma_strong.pdf", format="pdf", bbox_inches="tight")
No description has been provided for this image
In [21]:
# Figure 7 helper
def testOptimalRateProj(start=4, end=31, lc=2, mc=1):
    tau_results = defaultdict(list) 
    for n in range(start, end, 2):
        print(f"Testing optimal rate on {n} nodes")
        ls = np.ones(n) * lc
        ls[n-1] = np.inf
        mus = np.ones(n) * mc
        mus[n-1] = 0
        cases, names, Ws = getTestMatrices(n)
        for i, (Z, M) in enumerate(cases):
            _, tau = getReducedGamma(Z, M, ls, mus)
            tau_results[names[i]].append(tau)


    # Convert results to df
    tau_df = pd.DataFrame(tau_results)
    tau_df.index = range(start, end, 2)

    return tau_df
In [22]:
# Figure 7b
tau_df = testOptimalRateProj(start=4, end=31)

tau_df.to_csv("figs/fig_opt_gamma_proj.csv", index=False)
Testing optimal rate on 4 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 6 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 8 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 10 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 12 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 14 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 16 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 18 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 20 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 22 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 24 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 26 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 28 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 30 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
In [23]:
# Figure 7b
fig = plotTau(tau_df, "Contraction with an unrestricted monotone operator")

fig.savefig("figs/fig7b.pdf", format="pdf", bbox_inches="tight")
No description has been provided for this image

In figure 8 we examine the impact of operator ordering on the contraction factor. In this example (and previous ones), we illustrate the use of some of the prebuilt matrix functions.

getMT(n) returns the Malitsky-Tam algorithm design over $n$ operators

getRyu(n) returns the Tam extension of the Ryu algorithm design over $n$ operators

getFull(n) returns the fully connected algorithm with equal weights over $n$ operators

We also use a helper function getMfromWCholesky to return a valid $M \in \mathbf{R}^{n-1 \times n}$ such that $M^T M = W$

In [24]:
# Figure 8 - operator ordering
Lc=2
mu=1


taus = defaultdict(list)
for n in range(4, 31, 2):
    print(f"Testing optimal rate on {n} nodes")
    Lb, Wb = getBlockMin(n, n//2)
    Mb = getMfromWCholesky(Wb)
    Lmt, Wmt = getMT(n)
    Mmt = getMfromWCholesky(Wmt)
    Lr, Wr = getRyu(n)
    Mr = getMfromWCholesky(Wr)
    Lmax, Wmax = getFull(n)
    Mmax = getMfromWCholesky(Wmax)

    cases = [(Lb, Mb), (Lmt, Mmt), (Lr, Mr), (Lmax, Mmax)]
    names = ["2-Block", "MT", "Ryu", "Full"]
    ls = np.ones(n)*Lc
    ls[n-1] = np.inf
    mus = np.ones(n)*mu
    mus[n-1] = 0
    for i, (Z, M) in enumerate(cases):
        _, tau = getReducedGamma(Z, M, ls, mus)
        taus[names[i]].append(tau)

    ls = np.ones(n)*Lc
    ls[0] = np.inf
    mus = np.ones(n)*mu
    mus[0] = 0
    for i, (Z, M) in enumerate(cases):
        _, tau = getReducedGamma(Z, M, ls, mus)        
        taus[names[i]+" reverse"].append(tau)
Testing optimal rate on 4 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 6 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 8 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 10 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 12 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 14 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 16 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 18 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 20 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 22 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 24 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 26 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 28 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 30 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
In [25]:
# Figure 8 - operator ordering
df = pd.DataFrame(taus)
df.index = range(4, 31, 2)

# Plot the results
colors = ['blue', 'green', 'red', 'purple']
styles = ['b-', 'g-', 'k-', 'm-', 'y--', 'c--', 'r--', 'p--']
styles = ['b-', 'g-', 'k-', 'm-', 'b*-', 'g*-', 'k*-', 'm*-']

df.to_csv("figs/fig_function_ordering_opt.csv", index=False)
df.plot(style=styles)
plt.xlabel("Number of nodes")
plt.ylabel("Contraction")
plt.title("Operator Ordering and Splitting Performance")

plt.savefig("figs/fig_function_order_opt.pdf", format="pdf", bbox_inches="tight")
plt.show()
No description has been provided for this image

Figure 9 examines the impact of block count in the $d$-Block designs on the reduced contraction factor.

In [26]:
# Figure 9 - block size
# See 04_23_24_block_size.ipynb
# Function to generate list of all test matrices
def getTestMatricesBlocks(n):
    cases = []
    names = ['Full', 'MT']
    objs = ['Full', 'MT']
    blocksizes = ['', '']
    blocklist = ['', '']
    Lf, Wf = getFull(n)
    Mf = getMfromWCholesky(Wf)
    cases.append((Lf, Mf))
    Lmt, Wmt = getMT(n)
    Mmt = getMfromWCholesky(Wmt)
    cases.append((Lmt, Mmt))
    objstring = ['MinSLEM', 'MinResist', 'getMaxConnectivity', 'Min |Z-W|']
    for i in range(2, n//2+1):
        if n % i != 0:
            continue
        for j, obj in enumerate([getMinSLEM, getMinResist, getMaxConnectivity, getSimilar]):
            L, W = getBlockMin(n, i, objective=obj)
            M = getMfromWCholesky(W)
            cases.append((L, M))
            objs.append(objstring[j])
            blocksizes.append(i)
            blocklist.append(n//i)
            title = f"{n//i}-Block "+objstring[j]
            names.append(title)
        
    return cases, names, objs, blocksizes, blocklist

# Test function
def testMatrices(cases, names, lc=2, mu=1, gamma=0.5):
        
    taus = {}
    for i, (L, M) in enumerate(cases):
        ls = np.ones(len(L))*lc
        mus = np.ones(len(L))*mu
        
        gamma, tau = getReducedGamma(L, M, ls, mus)
        print(names[i], tau)
        taus[names[i]] = tau

    return taus

    
In [27]:
# Figure 9
results = []
for n in range(4, 25): #t < 120:
    print(n)
    cases, names, objs, blocksizes, blocks = getTestMatricesBlocks(n)
    taus = testMatrices(cases, names)
    # Each key in taus is a column, the row is the value of n
    for i in range(len(names)):
        k = names[i]
        v = taus[k]
        results.append({"n": n, "name": k, "obj": objs[i], "blocksize": blocksizes[i], "blocks":blocks[i], "tau": v})

df = pd.DataFrame(results)

# Save to csv
df.to_csv("figs/taus_plus.csv", index=False)
df.set_index('n', inplace=True)
4
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.4275726424387023
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.8002281453197694
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.5571563320386254
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714308439043
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.47232795740698197
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.42857142974429335
5
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.44769222096754585
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.861371784044431
6
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.45925820423443237
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.8973983347682633
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.7135742120391384
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.7182631442291072
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.7125769076136125
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.7146237387666267
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.5571562848351927
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714345044546
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.488471357684012
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.4285714294945974
7
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.46675734145403897
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.921028546326316
8
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.47200715470169324
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9373167138798217
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinSLEM 0.8309037714895217
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.8108953220221728
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block getMaxConnectivity 0.8002349980331156
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block Min |Z-W| 0.9414775041859474
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.5571562864004128
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714324225226
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.49712977590980384
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.4285717289200378
9
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.47588407918368214
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9490542144439524
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.7139323261601181
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.7182631341824306
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.7138583593905867
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.7154479936264707
10
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.4788623869914284
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9578086304484562
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinSLEM 0.8909710630474715
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinResist 0.867517704847014
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block getMaxConnectivity 0.8694665060801878
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block Min |Z-W| 0.8841704218835689
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.5571562868119515
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714375496707
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.5007530033260064
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.4285714341244909
11
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.48122091775576264
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9645090300427932
12
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.48313426706054324
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9697458591679796
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinSLEM 0.9274863710223136
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinResist 0.9043223463150312
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block getMaxConnectivity 0.914435584101685
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block Min |Z-W| 0.9723014749721509
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinSLEM 0.8306040572340888
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.8108995469244207
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block getMaxConnectivity 0.8002317783831558
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block Min |Z-W| 0.9732200751675371
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.713882481243341
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.7182631630830676
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.715230555842219
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.7154244052497442
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.5571562881070227
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714382736276
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.5048840996026825
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.42857143401716014
13
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.48471718030960137
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9739133518549759
14
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.4860481904482536
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9772819066072161
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block MinSLEM 0.9487402271176432
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block MinResist 0.927596295234003
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block getMaxConnectivity 0.9415108626363436
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block Min |Z-W| 0.9379760462197118
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.55715631881924
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714451273485
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.5053543651074622
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.42857144536092834
15
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.4871828194233909
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9800422357401884
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinSLEM 0.8909885842670557
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinResist 0.8675200794190076
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block getMaxConnectivity 0.8694664535695544
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block Min |Z-W| 0.8841748808659018
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.714146321224925
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.7182631419821576
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.7151833903650163
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.7154940849150406
16
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.4881613958305955
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9823315596735169
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block MinSLEM 0.9617907227701468
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block MinResist 0.943201687354377
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block getMaxConnectivity 0.9547829224265896
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block Min |Z-W| 0.9843154256403905
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinSLEM 0.8304099808829254
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.8108998689438812
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block getMaxConnectivity 0.8002305076130293
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block Min |Z-W| 0.9847811629257821
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.5571562810344565
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714541891736
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.5061192607260824
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.42857145632199684
17
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.4890140016796066
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9842506483710652
18
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.4897634138975941
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9858748663020437
No operators provided, using default LipschitzStronglyMonotoneOperator
9-Block MinSLEM 0.9703808977320246
No operators provided, using default LipschitzStronglyMonotoneOperator
9-Block MinResist 0.9543244267153969
No operators provided, using default LipschitzStronglyMonotoneOperator
9-Block getMaxConnectivity 0.9652620352983484
No operators provided, using default LipschitzStronglyMonotoneOperator
9-Block Min |Z-W| 0.9609559413334392
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinSLEM 0.9274863340035625
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinResist 0.9043221002381561
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block getMaxConnectivity 0.9144368470087124
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block Min |Z-W| 0.9877641370603041
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.7137591263162248
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.7182631394318443
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.7156777756433123
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.7151300240640917
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.5571562751598028
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.42857145889845066
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.5065757351760865
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.4285714592806289
19
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.49042725685598193
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9872613997715868
20
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.4910193660443159
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9884542931847442
No operators provided, using default LipschitzStronglyMonotoneOperator
10-Block MinSLEM 0.9764918849308651
No operators provided, using default LipschitzStronglyMonotoneOperator
10-Block MinResist 0.9624236294978088
No operators provided, using default LipschitzStronglyMonotoneOperator
10-Block getMaxConnectivity 0.9726910272407457
No operators provided, using default LipschitzStronglyMonotoneOperator
10-Block Min |Z-W| 0.9899039312877368
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinSLEM 0.8909604944000604
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinResist 0.8675196430955869
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block getMaxConnectivity 0.8694657973899463
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block Min |Z-W| 0.8841780055879428
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinSLEM 0.8306547100590185
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.8108995981763438
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block getMaxConnectivity 0.8002314011892808
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block Min |Z-W| 0.9902135583212976
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.5571562921308054
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.42857146164360865
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.5073479525629142
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.42857146229032794
21
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.4915507533342906
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9894878242816122
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block MinSLEM 0.9487432478204636
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block MinResist 0.9275962670135205
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block getMaxConnectivity 0.9415190793066045
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block Min |Z-W| 0.9379767047546463
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.7135615903063515
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.7182631426600574
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.7154026658832751
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.7151513652545484
22
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.4920302859111904
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9903890671244222
No operators provided, using default LipschitzStronglyMonotoneOperator
11-Block MinSLEM 0.980965610573116
No operators provided, using default LipschitzStronglyMonotoneOperator
11-Block MinResist 0.9685141496041315
No operators provided, using default LipschitzStronglyMonotoneOperator
11-Block getMaxConnectivity 0.9778676566839088
No operators provided, using default LipschitzStronglyMonotoneOperator
11-Block Min |Z-W| 0.9734129802157969
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.5571562777402097
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714662419582
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.509139759936115
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.4285714662517721
23
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.49246519297458935
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9911795563987065
24
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.49286136387228907
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9918767125507102
No operators provided, using default LipschitzStronglyMonotoneOperator
12-Block MinSLEM 0.9842233175864209
No operators provided, using default LipschitzStronglyMonotoneOperator
12-Block MinResist 0.9732178088466078
No operators provided, using default LipschitzStronglyMonotoneOperator
12-Block getMaxConnectivity 0.9816646293348918
No operators provided, using default LipschitzStronglyMonotoneOperator
12-Block Min |Z-W| 0.9929855588536252
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block MinSLEM 0.9617899149115514
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block MinResist 0.9432016721396277
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block getMaxConnectivity 0.9547828415390756
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block Min |Z-W| 0.9930940221228003
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinSLEM 0.9274864211025259
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinResist 0.9043224063558409
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block getMaxConnectivity 0.9144367580557783
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block Min |Z-W| 0.9931276194911502
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinSLEM 0.8310241286149925
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.8108982477568355
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block getMaxConnectivity 0.8002305222419616
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block Min |Z-W| 0.9931862824296942
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.7139332118231382
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.7182631402120128
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.7152482065411033
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.7152800293177907
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.5571562808428404
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714310144412
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.5099386151008687
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.42857147069365215
In [28]:
df[df["obj"].isin(["MinResist", "Full", "MT"])].groupby(['obj', 'blocks'])['tau'].groups.keys()
Out[28]:
dict_keys([('Full', ''), ('MT', ''), ('MinResist', 2), ('MinResist', 3), ('MinResist', 4), ('MinResist', 5), ('MinResist', 6), ('MinResist', 7), ('MinResist', 8), ('MinResist', 9), ('MinResist', 10), ('MinResist', 11), ('MinResist', 12)])
In [29]:
# Figure 9
# Load taus.csv
#df = pd.read_csv("taus.csv")
#df.loc[df['name'].isin(['Full', 'MT']), ['blocks', 'blocksize']] = ''

df[df["obj"].isin(["MinResist", "Full", "MT"])].groupby(['obj', 'blocks'])['tau'].plot(marker='o', linestyle='-', figsize=(10, 6))

keys = df[df["obj"].isin(["MinResist", "Full", "MT"])].groupby(['obj', 'blocks'])['tau'].groups.keys()
keys = ['Full', 'MT', '2-Block', '3-Block', '4-Block', '5-Block', '6-Block', '7-Block', '8-Block', '9-Block', '10-Block', '11-Block', '12-Block']
plt.legend(keys, bbox_to_anchor=(1, 1))
# Make x axis integer
plt.xticks(np.arange(4, 25, 2))
plt.xlabel(r"$n$")
plt.title("Min Resistance Contraction over $n$ Lipschitz Strongly Monotone Operators by Block Number")
plt.savefig("figs/fig_block_count.pdf", format="pdf", bbox_inches="tight")
No description has been provided for this image
In [30]:
# Figure 9 - Test function
def testMatricesProj(n, cases, names, lc=2, mu=1):
    ls = np.ones(n)*lc
    mus = np.ones(n)*mu
    ls[n-1] = np.inf
    mus[n-1] = 0
    taus = {}
    for i, (Z, M) in enumerate(cases):
        gamma, tau = getReducedGamma(Z, M, ls, mus)
        print(names[i], tau)
        taus[names[i]] = tau

    return taus
In [31]:
# Figure 9
projresults = []
for n in range(4,26): #t < 120:
    print(n)
    cases, names, objs, blocksizes, blocks = getTestMatricesBlocks(n)
    taus = testMatricesProj(n, cases, names)
    # Each key in taus is a column, the row is the value of n
    for i in range(len(names)):
        k = names[i]
        v = taus[k]
        
        projresults.append({"n": n, "name": k, "obj": objs[i], "blocksize": blocksizes[i], "blocks":blocks[i], "tau": v})

projdf = pd.DataFrame(projresults)
projdf.to_csv("figs/taus_proj.csv", index=False)
projdf.set_index('n', inplace=True)
4
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.7521521274547772
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9177841369745814
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.8191387832657023
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.7870338922103205
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.8005884142677305
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.7870338929300077
5
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.8044792127888197
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9475773165769197
6
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.838558740668551
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.963679040723567
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.9045196638648727
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.8989263093339976
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.9031665201664806
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.905811564931693
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.8708680920365564
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.8616700832103537
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.8648381115704538
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.8616700813867951
7
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.8625324131656744
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9733944272799456
8
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.8803148080938116
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9796953548701708
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinSLEM 0.947737890434155
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.9366150047051096
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block getMaxConnectivity 0.9409068724807719
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block Min |Z-W| 0.9733653867324151
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.899665656605118
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.897358435818429
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.897061358320355
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.8973584363622054
9
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.8940287042166419
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9840061423604513
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.9310037419763251
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.9226238048816924
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.9308683371509562
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.9329235479910636
10
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.904926183461662
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9870820594200824
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinSLEM 0.9690123429432841
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinResist 0.9580312775913491
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block getMaxConnectivity 0.9629973163283422
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block Min |Z-W| 0.9629875076136046
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.9180267565103261
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.9183673760071706
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.916691539095593
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9183673754845947
11
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9137934450814554
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9893521326451261
12
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9211491280506094
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9910743537751981
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinSLEM 0.9794372274110801
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinResist 0.9701555310266454
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block getMaxConnectivity 0.9756973937657129
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block Min |Z-W| 0.9901053735796335
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinSLEM 0.9594826252987537
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.9489711986480376
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block getMaxConnectivity 0.9564324332772989
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block Min |Z-W| 0.9875641251533125
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.946111764232151
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.9376136641003235
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.9476885966472107
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.9478983876149142
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.9307344399512485
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.9322246586548181
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.9300141945007564
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9322246586787853
13
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9273491859704499
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9924113648329533
14
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9326458422577715
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9934697819644993
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block MinSLEM 0.9854895183964308
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block MinResist 0.9778942636533086
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block getMaxConnectivity 0.9826255558805462
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block Min |Z-W| 0.9813969436642211
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.9400431051319559
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.9420552244966905
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.93962997966507
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9420552246279524
15
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9372231868414823
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9943217922541321
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinSLEM 0.9745905142273118
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinResist 0.9649800729638587
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block getMaxConnectivity 0.97109604331107
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block Min |Z-W| 0.9698496425926824
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.9561864907269577
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.9478753095788607
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.9572607197812847
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.9575677751837032
16
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9412182809698143
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9950176830139388
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block MinSLEM 0.9892332894570556
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block MinResist 0.9829428678594524
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block getMaxConnectivity 0.9871235320735171
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block Min |Z-W| 0.9951900483795266
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinSLEM 0.9674712824239583
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.9575260017395849
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block getMaxConnectivity 0.9660343274443299
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block Min |Z-W| 0.9928356727270506
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.9471521763588401
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.949393105826944
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.9469224619296801
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9493931076789771
17
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9447354996210365
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9955932803543736
18
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9478557853408256
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9960747909750525
No operators provided, using default LipschitzStronglyMonotoneOperator
9-Block MinSLEM 0.9917523264434918
No operators provided, using default LipschitzStronglyMonotoneOperator
9-Block MinResist 0.9865001993504064
No operators provided, using default LipschitzStronglyMonotoneOperator
9-Block getMaxConnectivity 0.9901485319734604
No operators provided, using default LipschitzStronglyMonotoneOperator
9-Block Min |Z-W| 0.9891810856357947
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinSLEM 0.9825424907370934
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinResist 0.9744372782099368
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block getMaxConnectivity 0.980233378159765
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block Min |Z-W| 0.9955573342108432
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.962597375900911
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.9552965512071064
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.9643509557600238
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.9639152809238458
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.9527572967367743
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.9550802030838836
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.9526415889172174
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9550802035807927
19
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9506426888675972
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9964816118850218
20
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9531469126958877
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.996828412190169
No operators provided, using default LipschitzStronglyMonotoneOperator
10-Block MinSLEM 0.9933657727548645
No operators provided, using default LipschitzStronglyMonotoneOperator
10-Block MinResist 0.989021596451965
No operators provided, using default LipschitzStronglyMonotoneOperator
10-Block getMaxConnectivity 0.9922094089430822
No operators provided, using default LipschitzStronglyMonotoneOperator
10-Block Min |Z-W| 0.997249101000427
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinSLEM 0.9784207691778445
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinResist 0.970002773290226
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block getMaxConnectivity 0.9767083047982691
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block Min |Z-W| 0.9748735391998931
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinSLEM 0.9721920253364399
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.9637516383755966
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block getMaxConnectivity 0.9724249952213602
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block Min |Z-W| 0.9953488150061929
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.957289303111209
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.9596176455084063
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.9572470127193968
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9596176491751938
21
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9554093767969893
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.997126427183303
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block MinSLEM 0.9874743349656987
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block MinResist 0.9805966853358046
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block getMaxConnectivity 0.9859614173482282
No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block Min |Z-W| 0.9837394037231179
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.9674384858366795
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.9608952673738462
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.9689905904689212
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.9688040622204398
22
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9574634693504176
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9973843798884913
No operators provided, using default LipschitzStronglyMonotoneOperator
11-Block MinSLEM 0.9945861395582486
No operators provided, using default LipschitzStronglyMonotoneOperator
11-Block MinResist 0.990885042528622
No operators provided, using default LipschitzStronglyMonotoneOperator
11-Block getMaxConnectivity 0.9936950430727856
No operators provided, using default LipschitzStronglyMonotoneOperator
11-Block Min |Z-W| 0.993050008194392
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.9610289962695392
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.9633222012559908
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.9610325830709481
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9633222012848819
23
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9593367015363936
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9976091357279269
24
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9610519693853622
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9978061502088273
No operators provided, using default LipschitzStronglyMonotoneOperator
12-Block MinSLEM 0.9954966157859618
No operators provided, using default LipschitzStronglyMonotoneOperator
12-Block MinResist 0.992309516634275
No operators provided, using default LipschitzStronglyMonotoneOperator
12-Block getMaxConnectivity 0.9947938451726746
No operators provided, using default LipschitzStronglyMonotoneOperator
12-Block Min |Z-W| 0.998250279297009
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block MinSLEM 0.9904306534939393
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block MinResist 0.984760973185923
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block getMaxConnectivity 0.9894469771429388
No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block Min |Z-W| 0.9978752519029023
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinSLEM 0.9855261836489811
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinResist 0.9776570058925739
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block getMaxConnectivity 0.9841645885838068
No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block Min |Z-W| 0.9974805118721081
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinSLEM 0.9756430702194357
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.9684466642077201
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block getMaxConnectivity 0.976317381794523
No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block Min |Z-W| 0.9967388078611039
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinSLEM 0.9715913534866777
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.9652615861028917
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.9725788339976896
No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.9726116359681148
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.964167231438586
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.9664039037809664
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block getMaxConnectivity 0.9642023236838992
No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9664039049575305
25
No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9626284123298885
No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9979798028064245
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinSLEM 0.9811923651156044
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinResist 0.9738455481401165
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block getMaxConnectivity 0.9805674621972678
No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block Min |Z-W| 0.9784107033253034
In [32]:
# Figure 9 Class 2 

#projdf = pd.read_csv("figs/taus_proj.csv")
projdf[projdf["obj"].isin(["MinResist", "Full", "MT"])].groupby(['obj', 'blocks'])['tau'].plot(marker='o', linestyle='-', figsize=(10, 6))

keys = ['Full', 'MT', '2-Block', '3-Block', '4-Block', '5-Block', '6-Block', '7-Block', '8-Block', '9-Block', '10-Block', '11-Block', '12-Block'] # If using df directly
plt.legend(keys, bbox_to_anchor=(1, 1))
plt.title("Min Resistance Contraction over $n-1$ Lipschitz Strongly Monotone Operators")
plt.savefig("figs/fig_block_count_proj.pdf", format="pdf", bbox_inches="tight")
No description has been provided for this image

Figure 10 combines the iteration time and contraction factor to depict how removing edges impacts algorithm design. We see that the 2-Block design strikes the optimal balance between connectivity (for faster contraction) and sparseness (for parallelism and faster iteration times)

This uses the getCycleTime function to return the iteration time.

In [33]:
# Figure 10 - pareto curves
# 04_21_24_full_pareto.ipynb

from matplotlib.colors import CenteredNorm
def getTaus(Z, W, l=None, mu=None):

    M = getMfromWCholesky(W)
    h = getReducedContractionFactor(Z, M, l, mu, gamma=0.5)
    m = getReducedGamma(Z, M, l, mu)[1]
    return h, m

def getContractTime(n, l, mu, objective=None, tol=0.5):
    Z_fixed = {}

    t = np.ones(n)
    ll = np.ones((n,n))
    results = {}
    for i in range(n//2):
        print(i)
        start = 0
        for k in range(2):
            for j in range(start, i + k*(n//2)):
                Z_fixed[(i + k*(n//2),j)] = 0
            Zs, Ws = objective(n, fixed_Z=Z_fixed)
            h, m = getTaus(Zs, Ws, l, mu)
            tt, _, _ = getCycleTime(t, ll, Zs, Ws, itrs=2)
            # r is number of entries in Z_fixed
            r = len(Z_fixed)
            tif = np.ceil(np.log(tol)/np.log(h)) # Total iterations fixed
            tio = np.ceil(np.log(tol)/np.log(m)) # Total iterations opt step
            ttf = tif*tt
            tto = tio*tt
            results[r] = {'Fixed':h , 'M Opt': m, 'Time': tt, 'Removed Edges': r, 'Fixed Total Iterations': tif, 'Opt Step Total Iterations': tio, 'Fixed Total Time': ttf, 'Opt Step Total Time': tto}
            print(results[r])
            start = n//2

    counter = 0
    for i in range(n//2 - 2):
        for j in range(i+1):
            r = n//2 + j
            c = n//2 - 1 - i + j
            Z_fixed[(r, c)] = 0
            # print(r,c)
            counter += 1
            if counter % 10 == 0:
                Ls, Ws = objective(n, fixed_Z=Z_fixed)
                h, m = getTaus(Ls, Ws, l, mu)
                tt = 4
                # r is number of entries in Z_fixed
                rem = len(Z_fixed)    
                tif = np.ceil(np.log(tol)/np.log(h)) # Total iterations fixed
                tio = np.ceil(np.log(tol)/np.log(m)) # Total iterations opt step
                ttf = tif*tt
                tto = tio*tt
                results[rem] = {'Fixed':h , 'M Opt': m, 'Time': tt, 'Removed Edges': rem, 'Fixed Total Iterations': tif, 'Opt Step Total Iterations': tio, 'Fixed Total Time': ttf, 'Opt Step Total Time': tto}
                print(results[rem])
    # Create dataframe of taus and times
    df = pd.DataFrame(results)

    return df
In [34]:
# Figure 10
n = 24
l = np.ones(n)*2
l[n-1] = np.inf
mu = np.ones(n)
mu[n-1]= 0

df = getContractTime(n, l, mu, objective=getMaxConnectivity)
df2 = df.T
0
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9798415277932965, 'M Opt': 0.9610519693854286, 'Time': 47.99999999999555, 'Removed Edges': 0, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1679.9999999998442, 'Opt Step Total Time': 863.99999999992}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9798415277932965, 'M Opt': 0.9610519693854286, 'Time': 47.99999999999555, 'Removed Edges': 0, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1679.9999999998442, 'Opt Step Total Time': 863.99999999992}
1
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9802934213873657, 'M Opt': 0.9611344883825657, 'Time': 46.00000000002653, 'Removed Edges': 1, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1610.0000000009286, 'Opt Step Total Time': 828.0000000004776}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9802906547272658, 'M Opt': 0.9612008911749754, 'Time': 44.00000000001398, 'Removed Edges': 2, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1540.0000000004893, 'Opt Step Total Time': 792.0000000002517}
2
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9803115290951551, 'M Opt': 0.9612841961043996, 'Time': 41.99999999999353, 'Removed Edges': 4, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1469.9999999997735, 'Opt Step Total Time': 755.9999999998835}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9803217939995267, 'M Opt': 0.9613404324143697, 'Time': 40.00000000033539, 'Removed Edges': 6, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1400.0000000117386, 'Opt Step Total Time': 720.000000006037}
3
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9803594772176855, 'M Opt': 0.9614511688616295, 'Time': 38.00000000019667, 'Removed Edges': 9, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1330.0000000068835, 'Opt Step Total Time': 684.0000000035401}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.980372539636585, 'M Opt': 0.9615160720131097, 'Time': 36.00000000005644, 'Removed Edges': 12, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1260.0000000019754, 'Opt Step Total Time': 648.0000000010159}
4
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9804160660741573, 'M Opt': 0.9616399278912013, 'Time': 34.00000000000092, 'Removed Edges': 16, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1224.000000000033, 'Opt Step Total Time': 612.0000000000165}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9803160087576462, 'M Opt': 0.9616502219370228, 'Time': 32.00000000018983, 'Removed Edges': 20, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1120.000000006644, 'Opt Step Total Time': 576.000000003417}
5
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9805064379875331, 'M Opt': 0.961814464869611, 'Time': 29.999999999934413, 'Removed Edges': 25, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1079.999999997639, 'Opt Step Total Time': 539.9999999988195}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9805369849158657, 'M Opt': 0.9618911233993571, 'Time': 28.000000000015866, 'Removed Edges': 30, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1008.0000000005712, 'Opt Step Total Time': 504.0000000002856}
6
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9805587441177257, 'M Opt': 0.9619696358597921, 'Time': 26.000000000192202, 'Removed Edges': 36, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 936.0000000069192, 'Opt Step Total Time': 468.0000000034596}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.980616569578718, 'M Opt': 0.9620812351430117, 'Time': 23.9999999999246, 'Removed Edges': 42, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 863.9999999972856, 'Opt Step Total Time': 431.9999999986428}
7
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9805803035541303, 'M Opt': 0.9622244218627922, 'Time': 22.000000000001247, 'Removed Edges': 49, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 792.0000000000449, 'Opt Step Total Time': 418.0000000000237}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9806097718667652, 'M Opt': 0.962304209896036, 'Time': 19.99999999987995, 'Removed Edges': 56, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 719.9999999956782, 'Opt Step Total Time': 379.99999999771904}
8
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9806706661849034, 'M Opt': 0.9624258907775105, 'Time': 17.999999999943523, 'Removed Edges': 64, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 647.9999999979668, 'Opt Step Total Time': 341.9999999989269}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9807015913368081, 'M Opt': 0.9624910820032222, 'Time': 15.999999999994685, 'Removed Edges': 72, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 575.9999999998087, 'Opt Step Total Time': 303.99999999989905}
9
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9808093208404102, 'M Opt': 0.9627105025485819, 'Time': 14.000000000000364, 'Removed Edges': 81, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 504.00000000001313, 'Opt Step Total Time': 266.00000000000693}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9808410860902486, 'M Opt': 0.9627679103016183, 'Time': 11.9999999999999, 'Removed Edges': 90, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 431.9999999999964, 'Opt Step Total Time': 227.99999999999812}
10
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9810230598007482, 'M Opt': 0.9630429010126391, 'Time': 10.000000000165418, 'Removed Edges': 100, 'Fixed Total Iterations': 37.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 370.00000000612044, 'Opt Step Total Time': 190.00000000314293}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9810393061934247, 'M Opt': 0.9630413776592525, 'Time': 7.999999999999933, 'Removed Edges': 110, 'Fixed Total Iterations': 37.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 295.99999999999756, 'Opt Step Total Time': 151.99999999999872}
11
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.981364177730722, 'M Opt': 0.9642038633941726, 'Time': 3.999999999999991, 'Removed Edges': 121, 'Fixed Total Iterations': 37.0, 'Opt Step Total Iterations': 20.0, 'Fixed Total Time': 147.99999999999966, 'Opt Step Total Time': 79.99999999999983}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.981365178730152, 'M Opt': 0.9642023236908612, 'Time': 3.999999999999991, 'Removed Edges': 132, 'Fixed Total Iterations': 37.0, 'Opt Step Total Iterations': 20.0, 'Fixed Total Time': 147.99999999999966, 'Opt Step Total Time': 79.99999999999983}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9838400144307651, 'M Opt': 0.9652843389466005, 'Time': 4, 'Removed Edges': 142, 'Fixed Total Iterations': 43.0, 'Opt Step Total Iterations': 20.0, 'Fixed Total Time': 172.0, 'Opt Step Total Time': 80.0}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9853883455134209, 'M Opt': 0.966900228979608, 'Time': 4, 'Removed Edges': 152, 'Fixed Total Iterations': 48.0, 'Opt Step Total Iterations': 21.0, 'Fixed Total Time': 192.0, 'Opt Step Total Time': 84.0}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9868013536962403, 'M Opt': 0.9686471381342026, 'Time': 4, 'Removed Edges': 162, 'Fixed Total Iterations': 53.0, 'Opt Step Total Iterations': 22.0, 'Fixed Total Time': 212.0, 'Opt Step Total Time': 88.0}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9886689488722984, 'M Opt': 0.9699045174130262, 'Time': 4, 'Removed Edges': 172, 'Fixed Total Iterations': 61.0, 'Opt Step Total Iterations': 23.0, 'Fixed Total Time': 244.0, 'Opt Step Total Time': 92.0}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9912681529407553, 'M Opt': 0.9724134559398137, 'Time': 4, 'Removed Edges': 182, 'Fixed Total Iterations': 80.0, 'Opt Step Total Iterations': 25.0, 'Fixed Total Time': 320.0, 'Opt Step Total Time': 100.0}
In [35]:
df.to_csv('figs/n24.csv', index=False)
# df = pd.read_csv("figs/n24.csv")

# Plot total time vs removed edges
plt.plot(df.iloc[3], df.iloc[6], df.iloc[3], df.iloc[7])
# Subtitle
plt.suptitle('Time Units to 0.5 Contraction vs Removed Edges, $n=$'+str(n))


plt.legend( ['Fixed Step Size', 'Optimal Step Size'])
plt.xlabel('Removed Edges')
plt.ylabel('Time Units')
plt.savefig("figs/fig_optimal_sparsity.pdf", format="pdf", bbox_inches="tight")
plt.show()
No description has been provided for this image
In [36]:
# Figure 10
# Plot the top three rows of df as a function of time with points annotated
plt.plot(df.iloc[2], df.iloc[0], marker='<')
plt.plot(df.iloc[2], df.iloc[1], marker='<')

plt.title('Contraction vs Time as Edges are Removed')
# Add legend
plt.legend( ['Fixed Step Size', 'Optimal Step Size'])
# Annotate points with number of removed edges
lx, ly = (0,0)
right = 0
up = 10
for j in range(len(df.columns)):
        print(j,(df.iloc[2,j], df.iloc[1,j]))
        if df.iloc[2,j] < 4:
                right = 10
                up = 1
        if df.iloc[2,j] == 4.0:
                up = 0
        if abs(lx - df.iloc[2,j]) > 1 or abs(ly - df.iloc[1,j]) > 0.001:
                plt.annotate(df.columns[j], (df.iloc[2,j], df.iloc[0,j]), textcoords="offset points", xytext=(right,up), ha='center', fontsize=8)
                plt.annotate(df.columns[j], (df.iloc[2,j], df.iloc[1,j]), textcoords="offset points", xytext=(right,up), ha='center', fontsize=8)
                lx = df.iloc[2,j]
                ly = df.iloc[1,j]
        
# Annotate with points

plt.xlabel('Average Iteration Time')
plt.ylabel(r'Contraction Rate ($\tau$)')

plt.savefig("figs/fig_pareto.pdf", format="pdf", bbox_inches="tight")
plt.show()
0 (47.99999999999555, 0.9610519693854286)
1 (46.00000000002653, 0.9611344883825657)
2 (44.00000000001398, 0.9612008911749754)
3 (41.99999999999353, 0.9612841961043996)
4 (40.00000000033539, 0.9613404324143697)
5 (38.00000000019667, 0.9614511688616295)
6 (36.00000000005644, 0.9615160720131097)
7 (34.00000000000092, 0.9616399278912013)
8 (32.00000000018983, 0.9616502219370228)
9 (29.999999999934413, 0.961814464869611)
10 (28.000000000015866, 0.9618911233993571)
11 (26.000000000192202, 0.9619696358597921)
12 (23.9999999999246, 0.9620812351430117)
13 (22.000000000001247, 0.9622244218627922)
14 (19.99999999987995, 0.962304209896036)
15 (17.999999999943523, 0.9624258907775105)
16 (15.999999999994685, 0.9624910820032222)
17 (14.000000000000364, 0.9627105025485819)
18 (11.9999999999999, 0.9627679103016183)
19 (10.000000000165418, 0.9630429010126391)
20 (7.999999999999933, 0.9630413776592525)
21 (3.999999999999991, 0.9642038633941726)
22 (3.999999999999991, 0.9642023236908612)
23 (4.0, 0.9652843389466005)
24 (4.0, 0.966900228979608)
25 (4.0, 0.9686471381342026)
26 (4.0, 0.9699045174130262)
27 (4.0, 0.9724134559398137)
No description has been provided for this image

Figure 11 just shows how we removed the edges

In [37]:
# Figure 11 - edge deletion ordering
# 04_21_24_full_pareto.ipynb

def cplot(M, c, title=''):
    vmin = 1
    vmax = np.max(ordermat)
    cm = plt.cm.viridis #coolwarm
    fig, ax = plt.subplots(1, 1, figsize=(12, 6))
    x = np.arange(n)
    y = -np.arange(n)
    pc = ax.pcolormesh(x, y, M, cmap=cm , vmin=vmin, vmax=vmax)
    ax.set_title(title) #'Edge Removal Ordering'
    ax.axis('off')
    ax.set_aspect('equal')

    # Add colorbar
    plt.tight_layout()
    
    cbar = fig.colorbar(pc) 
    cbar.set_ticks(np.arange(1, c, 4)) 
    return fig

# Display edge removal ordering
def order_graph(n):
    order_matrix = np.zeros((n,n)) 
    counter = 1
    for i in range(n//2):
        start = 0
        for k in range(2):
            for j in range(start, i + k*(n//2)):
                r = i + k*(n//2)
                c = j
                order_matrix[(r,j)] = counter
                order_matrix[(c,r)] = counter
            
            counter += 1
            start = n//2

    ccounter = 0
    for i in range(n//2 - 2):
        for j in range(i+1):
            r = n//2 + j
            c = n//2 - 1 - i + j
            order_matrix[(r, c)] = counter
            order_matrix[(c, r)] = counter
            ccounter += 1
            if ccounter % 10 == 0:
                counter += 1
            
    return order_matrix, counter
ordermat, c = order_graph(24)
ordermat = np.ma.masked_array(ordermat, ordermat < 1)

fig = cplot(ordermat, c, 'Edge Removal Ordering')
fig.savefig("figs/fig_edge_removal.pdf")
No description has been provided for this image

Figure 12 then combines the iteration time and contraction factor to find the total time required for a given contraction level, and compares the 2-Block design with the constrained minimum iteration time design, using the minimum total effective resistance objective for each.

It demonstrates some additional parameters in the getMinCycle function. minW=n//2 sets the minimum number of edges for each node in the graph of $W$ to be $\frac{n}{2}$, which we call the constrained minimum iteration time design.

We also introduce the getMetrics function, which returns the iteration time, contraction factor, total cycles, and total time for a given contraction target, over a given design ($Z, W$), compute and communication times ($t, l$), and operator parameters (using the default values in Class 1).

In [38]:
# Figure 12
block_results = []
min_results = []
for n in range(6,10):
    for i in range(40):
        t = np.random.rand(n)*10+1

        # Communication time
        l = np.random.rand(n, n)*1.5 + 0.5
        l = np.tril(l, -1) + np.tril(l, -1).T
        Zb, Wb = getBlockMin(n, n//2, objective=getMinResist)
        c, tau, cc, tt = getMetrics(Zb, Wb, t, l,contraction_target=0.01)
        block_results.append((n, i, c, tau, cc, tt))
        Z, W = getMinCycle(n, objective=getMinResist, t=t, l=l, c=0.01, r=n, minW=n//2)
        if Z is not None:
            c, tau, cc, ttc = getMetrics(Z, W, t, l,contraction_target=0.01)
        else:
            c, tau, cc, ttc = (None, None, None, None)
        min_results.append((n, i, c, tau, cc, ttc))
        print(n,i,tt,ttc)
        
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 0 557.3531756387047 557.3531756387047
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 1 618.6495759991482 522.5575943515803
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 2 634.3218614903401 634.3218614903401
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 3 641.4972132053769 641.4972132053769
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 4 698.1699747774383 698.1699747774383
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 5 569.515050838532 569.515050838532
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 6 376.9690001044985 376.9690001044985
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 7 670.5283718479254 670.5283718479254
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 8 507.01508244742433 507.01508244742433
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 9 611.8972113276575 611.8972113276575
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 10 515.4564016623426 515.4564016623426
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 11 352.0906040555003 352.0906040555003
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 12 680.7878167672559 574.9216073169277
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 13 681.9161056083263 681.9161056083263
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 14 438.6224794087684 379.782237023701
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 15 469.9423249042196 469.9423249042196
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 16 402.9427894920025 402.9427894920025
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 17 449.5968783117114 449.5968783117114
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 18 631.2345788947955 631.2345788947955
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 19 687.8450367311013 687.8450367311013
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 20 584.4949444173751 584.4949444173751
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 21 558.0322472678686 558.0322472678686
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 22 646.9648993960004 447.35087379702185
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 23 574.2226850876073 574.2226850876073
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 24 535.5991330142116 535.5991330142116
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 25 671.5533664181501 586.7247247959613
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 26 639.556728748259 550.1469009686596
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 27 576.6433913510302 502.9007834235641
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 28 466.0642505231957 466.0642505231957
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 29 391.35156144266284 391.35156144266284
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 30 641.0226077756681 502.83716644362454
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 31 536.7520175141719 434.8958176080492
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 32 622.749991390554 622.749991390554
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 33 697.1623001438152 590.4176839105232
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 34 715.8345026940582 715.8345026940582
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 35 391.3247675479266 320.9993232783132
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 36 693.0730278000117 693.0730278000117
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 37 493.0795606995162 493.0795606995162
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 38 642.2496924335782 642.2496924335782
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
6 39 599.9964444890811 480.4773703561166
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 0 1009.7815502095045 623.4558572405037
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 1 1201.8065590682431 843.5666502620925
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 2 1145.6308131959015 859.5487455351755
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 3 947.4243044848237 713.1464291507109
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 4 920.8715257245128 642.1624468584259
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 5 655.1522775740241 802.2272786490657
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 6 1134.1154005209337 801.3685291961183
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 7 879.6441339560961 630.507661225084
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 8 1091.5053013834986 801.9222622444554
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 9 964.291619336055 637.1228731274556
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 10 1153.956774454247 858.2519390280017
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 11 890.2875453601291 672.2579424198811
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 12 1096.2046903002793 715.9773486051874
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 13 1070.5345343515824 778.811978080118
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 14 1035.5370276507733 846.687221736514
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 15 842.6281977445385 556.1096599226321
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 16 912.5942510067605 650.3648764610027
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 17 824.7190175821274 762.232543308557
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 18 969.228435560242 648.9540203521324
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 19 914.1653817607349 817.1828461036378
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 20 965.2400815544374 709.1555036140071
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 21 1156.7626981094122 875.6651395475794
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 22 1028.7596831480432 755.8234406809379
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 23 1094.0323711256517 735.8977759921172
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 24 987.7113435932681 877.2977972245396
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 25 1027.2736179436215 766.6698300592236
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 26 1057.7269452834619 813.4167944094968
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 27 977.4607632692446 836.4638762127402
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 28 791.9518623611318 547.2774913509172
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 29 998.9606350146001 750.1787685278255
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 30 981.6537449328875 741.2487461769741
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 31 1158.0924631019589 769.9113371318736
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 32 956.3123962294344 700.507671237666
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 33 761.0811635510308 515.5482941855594
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 34 796.6594732631575 598.2701796150238
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 35 1082.936177156431 796.8686706328905
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 36 887.6253880272725 614.2798370554196
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 37 1153.9034714510924 1023.530182114337
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 38 820.2557109131238 770.0359739014427
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
7 39 936.4046944131035 811.3183457179131
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 0 778.3397473458791 778.3397473458791
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 1 931.3660108877552 931.3660108877552
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 2 908.4394300816159 908.4394300816159
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 3 1041.3379427886944 856.3930519515962
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 4 871.4342775781261 871.4342775781261
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 5 850.6989835614263 670.9498570762278
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 6 887.3557897689439 887.3557897689439
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 7 920.8772236131991 920.8772236131991
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 8 943.7214241050503 943.7214241050503
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 9 987.6096517203971 845.8357282580005
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 10 875.6381419983431 722.2454910197346
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 11 986.322043729115 986.322043729115
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 12 861.6899111945168 720.1562322940163
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 13 788.7211125229427 788.7211125229427
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 14 917.2799372835626 917.2799372835626
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 15 944.0450336283072 944.0450336283072
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 16 906.1056960434966 755.5509489068345
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 17 971.1858977012915 971.1858977012915
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 18 1010.9826696179744 1010.9826696179744
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 19 973.7568330509746 973.7568330509746
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 20 758.1515803222592 706.1069606299252
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 21 956.9002336963649 884.2695705966117
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 22 917.1738005707653 917.1738005707653
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 23 611.5636068897693 611.5636068897693
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 24 947.3587883796454 947.3587883796454
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 25 959.6749501212437 959.6749501212437
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 26 798.642723049982 798.642723049982
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 27 755.2356205115374 680.2153843515109
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 28 871.6707451189536 871.6707451189536
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 29 1011.0537713146791 1011.0537713146791
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 30 949.0195830383495 719.6255055421284
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 31 818.3700512676226 818.3700512676226
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 32 987.6596784885056 987.6596784885056
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 33 904.6457929185774 904.6457929185774
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 34 781.7442794868281 734.6786220698642
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 35 721.8061592582985 628.4237756294692
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 36 839.0214391230143 839.0214391230143
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 37 973.9200485594929 973.9200485594929
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 38 895.0188088120344 895.0188088120344
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
8 39 783.8552945310688 613.4379259997809
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 0 1254.3220674725992 906.7988521573361
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 1 1276.351145350438 997.1872254269489
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 2 1116.1432991760576 878.2766944428877
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 3 1418.989552484359 1015.0759854496991
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 4 1191.6506624970289 1523.7500301935197
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 5 1391.810325126577 1095.1950099327642
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 6 1316.1890348950299 980.5058682022782
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 7 1530.9143631044203 919.1728272512466
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 8 1389.2737931499328 1093.1990503867291
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 9 1230.8809460978837 867.0100337855438
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 10 1173.5241369254095 849.7477488078184
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 11 1378.1317049542104 953.8722803054234
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 12 1163.894999712936 896.7715576115384
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 13 1275.4440953218545 980.9006570250478
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 14 1398.2278631972194 1003.0954761348794
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 15 1050.7988297568377 600.7778510931678
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 16 1011.421738391258 1077.7444749856534
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 17 1368.6247759961773 1058.5034933550446
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 18 1232.035399371981 865.966429542229
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 19 1321.1751054851338 1277.8578884005497
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 20 1448.3797976146698 1017.3230403319209
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 21 1439.708013196225 1080.562288192114
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 22 1216.6704131775964 884.5922371129849
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 23 1348.93208071445 996.9290304282686
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 24 1264.5398888907396 800.8907987028069
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 25 1440.0590426928093 929.814586081895
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 26 1418.1136400332998 831.4045368645209
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 27 1248.1736047928566 967.559049199994
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 28 1243.1472587309083 1073.5042143858855
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 29 1354.019138928614 1065.4576831171744
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 30 1292.997356682974 771.5855441536868
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 31 1341.8157971282185 972.3020323513883
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 32 1541.8228632480113 1039.2316369260504
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 33 766.3023077543863 979.8619674361797
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 34 1385.6760107130713 1340.244010308109
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 35 1398.588412707733 1042.228782007279
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 36 1412.6165398163778 1024.4818313434662
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 37 1163.4922838390758 840.8499359932923
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 38 1317.6194293430312 904.2595731915733
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
9 39 1092.0057622338984 800.2356482873975
In [39]:
# Figure 12
block_df = pd.DataFrame(block_results)
min_df = pd.DataFrame(min_results)

block_df.to_csv('figs/block_df2.csv')
min_df.to_csv('figs/min_cycle_min_edge.csv')
In [40]:
# Paired density chart for block vs min cycle
# Figure 12
# block_df = pd.read_csv('figs/block_df2.csv')
# min_df = pd.read_csv('figs/min_cycle_min_edge.csv')
fig, axs = plt.subplots(2, 2, sharey=True)
n = 6
key = 5 #'5' #use string if loading from csv
start = 0
for i in range(2):
    for j in range(2):
        end = 40 + start
        axs[i,j] = block_df[key][start:end].plot.kde(ax=axs[i,j], color='blue')
        min_df[key][start:end].plot.kde(ax=axs[i,j], color='red')
        start += 40
        axs[i,j].set_title(r"$n=$"+str(n))
        n += 1

fig.legend([r'$d$-Block Design', 'Con. Min Iter Time'], loc=(.65,.8))

for ax in axs.flat:
    ax.set(xlabel='Time')
for ax in fig.get_axes():
    ax.label_outer()
fig.savefig("figs/fig_constrained_mincycle_histogram.pdf", format="pdf", bbox_inches="tight")
No description has been provided for this image
In [ ]: